<?php
/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: TreeMap.php 14 2006-11-28 22:05:19Z rdff3 $
 */
/**
 *
 */
require_once( "util/AbstractMap.php" );
require_once( "util/SortedMap.php" );
require_once( "util/Iterator.php" );
require_once( "lang/Comparable.php" );
require_once( "util/MapEntry.php" );

define("BLACK", "BLACK" );
define("RED", "RED" );
/** 
 * Class TreeMap
 *
 * Red-Black tree based implementation of the SortedMap interface. This class guarantees that the map will be in ascending key 
 * order, sorted according to the natural order for the key's class (see Comparable), or by the comparator provided at creation 
 * time, depending on which constructor is used.
 * 
 * This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are
 * adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.
 * 
 * Note that the ordering maintained by a sorted map (whether or not an explicit comparator is provided) must be consistent with 
 * equals if this sorted map is to correctly implement the Map interface. (See Comparable or Comparator for a precise definition 
 * of consistent with equals.) This is so because the Map interface is defined in terms of the equals operation, but a map performs 
 * all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the 
 * standpoint of the sorted map, equal. The behavior of a sorted map is well-defined even if its ordering is inconsistent with 
 * equals; it just fails to obey the general contract of the Map interface.
 * 
 * Note that this implementation is not synchronized. If multiple threads access a map concurrently, and at least one of the 
 * threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that 
 * adds or deletes one or more mappings; merely changing the value associated with an existing key is not a structural modification.) 
 * This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, 
 * the map should be "wrapped" using the Collections.synchronizedMap method. This is best done at creation time, to prevent 
 * accidental unsynchronized access to the map:
 *      
 * Map m = Collections.synchronizedMap(new TreeMap(...));
 * 
 * The iterators returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at 
 * any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator 
 * throws a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, 
 * rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
 * 
 * Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any 
 * hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw 
 * ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on 
 * this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
 * 
 * This class is a member of the PHP Collections Framework. 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: TreeMap.php 14 2006-11-28 22:05:19Z rdff3 $
 */ 
class TreeMap extends AbstractMap implements SortedMap {

	
	protected $entry_set = null;
	
	/**
	 * The Comparator used to maintain order in this TreeMap, or null if this TreeMap uses its elements natural ordering.
	 */
	protected $comparator = null;
	
	protected $root = null;
	
	/**
	 * The number of entries in the tree.
	 */
	protected $size = 0;
	
	/** 
	 * The number of structural modifications to the tree.
	 */
	protected $modCount = 0;
	
	/** 
	 * Returns the number of structural modifications to the tree.
	 */
	public function getModCount() {
		return $this->modCount;
	}
		
	private function incrementSize() {
		$this->size++;
		$this->modCount++;
	}
	private function decrementSize() {
		$this->size--;
		$this->modCount++;
	}
	
	/**
	 * Constructs a new, empty map, sorted according to the given comparator.
	 *
	 * Constructs a new, empty map, sorted according to the given comparator. All keys inserted into the map must be mutually 
	 * comparable by the given comparator: comparator.compare(k1, k2) must not throw a ClassCastException for any keys k1 and k2 
	 * in the map. If the user attempts to put a key into the map that violates this constraint, the put(Object key, Object value) 
	 * call will throw a ClassCastException.
	 * 
	 * @param Comparator $c the comparator that will be used to sort this map.  A null value indicates that the keys' natural
	 *		ordering should be used.
	 */
	public function __construct( Comparator $c = null ) {
		$this->comparator = $c;
	}
	
	/**
	 * Returns the number of key-value mappings in this map.
	 *
	 * @returns int the number of key-value mappings in this map.
	 */
	public function size() {
		return $this->size;
	}
	
	/**
	 * Returns true if this map contains a mapping for the specified key.
	 *
	 * @param Object $key key whose presence in this map is to be tested.
	 * @returns boolean true if this map contains a mapping for the specified key.
	 * @throws ClassCastException - if the key cannot be compared with the keys currently in the map. 
	 * @throws NullPointerException - key is null and this map uses natural ordering, or its comparator does not tolerate null keys.
	 */
	public function containsKey( Object $key ) {
		return $this->getEntry( $key ) != null;
	}
	
	/**
	 * Returns true if this map maps one or more keys to the specified value.
	 *
	 * More formally, returns true if and only if this map contains at least one mapping to a value v such that (value==null ?
	 * v==null : value.equals(v)). This operation will probably require time linear in the Map size for most implementations of Map.
	 *
	 * @param Object $value value whose presence in this Map is to be tested.
	 * @returns boolean true if a mapping to value exists; false otherwise.
	 */
	public function containsValue( Object $value ) {
		if ( $this->root == null )
			return false;
		elseif ( $value == null )
			return valueSearchNull( $this->root );
		else	
			return valueSearchNonNull( $this->root, $value );
	}
	
	private function valueSearchNull ( TreeMap_Entry $n ) {
		if ($n->value == null)
			return true;
		
		$return_val = 	( $n->left != null && $this->valueSearchNull( $n->left )) || 
						( $n->right != null && $this->valueSearchNull( $n->right ));
		return $return_val;
	}
	
	private function valueSearchNonNull ( TreeMap_Entry $n, Object $value ) {
		if ( $value->equals( $n->value ))
			return true;
		
		$return_val = 	( $n->left != null && $this->valueSearchNonNull( $n->left, $value )) || 
						( $n->right != null && $this->valueSearchNonNull( $n->right, $value ));
		return $return_val;
	}
	
	/** 
	 * Returns the value to which this map maps the specified key.
	 *
	 * Returns null if the map contains no mapping for this key. A return value of null does not necessarily indicate that the 
	 * map contains no mapping for the key; it's also possible that the map explicitly maps the key to null. The containsKey  
	 * operation may be used to distinguish these two cases.
	 * 
	 * @param Object $key key whose associated value is to be returned.
	 * @returns Object the value to which this map maps the specified key, or null if the map contains no mapping for the key.
	 * @throws ClassCastException - key cannot be compared with the keys currently in the map. 
	 * @throws NullPointerException - key is null and this map uses natural ordering, or its comparator does not tolerate null keys.
	 * 
	 */
	public function get( Object $key ) {
		$p = $this->getEntry( $key );
		return ($p == null ? null : $p->value);
	}
	
	/**
	 * Returns the comparator used to order this map, or null if this map uses its keys' natural order.
	 *
	 * @returns Comparator the comparator associated with this sorted map, or null if it uses its keys' natural sort method.
	 */
	public function comparator() {
		return $this->comparator;
	}
	
	/**
	 * Returns the first (lowest) key currently in this sorted map.
	 *
	 * @returns Object the first (lowest) key currently in this sorted map.
	 * @throws NoSuchElementException - Map is empty.
	 */
	public function firstKey() {
		return $this->key( $this->firstEntry() );
	}
	
	/**
	 * Returns the last (highest) key currently in this sorted map.
	 *
	 * @returns Object the last (highest) key currently in this sorted map.
	 * @throws NoSuchElementException - Map is empty.
	 */
	public function lastKey() {
		return $this->key( $this->lastEntry() );
	}
	
	/**
	 * Copies all of the mappings from the specified map to this map.
	 *
	 * These mappings replace any mappings that this map had for any of the keys currently in the specified map.
	 *
	 * @param Map $map mappings to be stored in this map.
	 * @throws ClassCastException - class of a key or value in the specified map prevents it from being stored in this map.
	 * @throws NullPointerException - if the given map is null or this map does not permit null keys and a key in the specified
	 *		map is null.
	 */
	public function putAll( Map $map ) {
		$map_size = $map->size();
		
		if ( $this->size() == 0 && $map_size != 0 && $map instanceof SortedMap) {
			$c = $map->comparator();
			if ($c == $this->comparator() || ($c != null && $c->equals( $this->comparator()))) {
				$this->modCount++;
				try {
					$this->buildFromSorted( $map_size, $map->entrySet()->iterator(), null, null);
				}
				catch ( IOException $cannotHappen ) { }
				catch ( ClassNotFoundException $cannotHappen ) { }
				return;
			}
		}
		return parent::putAll( $map );
	}
	
	/**
	 * Returns this map's entry for the given key, or null if the map does not contain an entry for the key.
	 *
	 * @returns mixed this map's entry for the given key, or null if the map does not contain an entry for the key.
	 * @throws ClassCastException if the key cannot be compared with the keys
	 * 		currently in the map.
	 * @throws NullPointerException key is &lttt&gtnull</tt> and this map uses
	 * 		natural order, or its comparator does not tolerate null keys.
 	 */ 
	private function getEntry( Object $key ) {
		$p = $this->root;
		while ($p != null) {
			$cmp = $this->compare( $key, $p->key);
			if ($cmp == 0)
				return $p;
			else if ($cmp > 0)
				$p = $p->left;
			else
				$p = $p->right;
		}
		return null;
	}
	/**
	 * Gets the entry corresponding to the specified key; if no such entry
	 * exists, returns the entry for the least key greater than the specified
	 * key; if no such entry exists (i.e., the greatest key in the Tree is less
	 * than the specified key), returns null.
	 */ 
	private function getCeilEntry( Object $key ) {
		$p = $this->root;
		if ($p == null)
			return null;
			
		while (true) {
			$cmp = $this->compare( $key, $p->key );
			if ($cmp == 0) {
				return $p;
			}
			else if ($cmp < 0) {
				if ($p->left != null)
					$p = $p->left;
				else
					return $p;
			}
			else {
				if ($p->right != null) {
					$p = $p->right;
				}
				else {
					$parent = $p->parent;
					$ch = $p;
					while ($parent != null && $ch == $parent->right) {
						$ch = $parent;
						$parent = $parent->parent;
					}
					return $parent;
				}
			}
		}
	}
	/**
	 * Returns the entry for the greatest key less than the specified key; if
	 * no such entry exists (i.e., the least key in the Tree is greater than
	 * the specified key), returns null.
	 */ 
	private function getPrecedEntry( Object $key ) {
		$p = $this->root;
		if ($p == null)
			return null;
			
		while (true) {
			$cmp = $this->compare( $key, $p->key);
			if ($cmp > 0) {
				if ($p->right != null)
					$p = $p->right;
				else
					return $p;
			} else {
				if ($p->left != null) {
					$p = $p->left;
				} else {
					$parent = $p->parent;
					$ch = $p;
					while ($parent != null && $ch == $parent->left) {
						$ch = $parent;
						$parent = $parent->parent;
					}
					return $parent;
				}
			}
		}
	}

	/**
	 * Returns the key corresonding to the specified Entry. Throw
	 * NoSuchElementException if the Entry is null.
	 */ 
	private static function key( TreeMap_Entry $e ) {
		if ($e == null)
			throw new NoSuchElementException();
		return $e->key;
	}
	
	
	/**
	 * Associates the specifed value with the specified key in this map. 
	 *
	 * If the map previously contained a mapping for this key, the old value is replaced.
	 *
	 * @param Object $key key with which the specified value is to be associated.
	 * @param Object $value value to be associated with the specified key.
	 * @returns Object previous value associated with specified key, or null if there was no mapping for this key.  A null return
	 *		can also indicate that the map previously associated null with the specified key.
	 * @throws ClassCastException - key cannot be compared with the keys currently in the map.
	 * @throws NullPointerException - key is null and this map uses natural order, or its comparator does not tolerate null keys.
	 */
	public function put( Object $key, Object $value) {
		$t = $this->root;
		
		if ($t == null) {
			$this->incrementSize();
			$this->root = new TreeMap_Entry( $key, $value, null );
			return null;
		}
		
		while (true) {
			$cmp = $this->compare($key, $t->key);
			if ($cmp == 0) {
				return $t->setValue( $value );
			} else if ($cmp < 0) {
				if ($t->left != null) {
					$t = $t->left;
				} else {
					$this->incrementSize();
					$t->left = new TreeMap_Entry( $key, $value, $t );
					$this->fixAfterInsertion( $t->left );
					return null;
				}
			} else { // $cmp > 0
				if ($t->right != null) {
					$t = $t->right;
				} else {
					$this->incrementSize();
					$t->right = new TreeMap_Entry( $key, $value, $t);
					$this->fixAfterInsertion( $t->right );
					return null;
				}
			}
		}
	}
	
	/**
	 * Removes the mapping for this key from this TreeMap if present.
	 *
	 * @param Object $key key for which mapping should be removed.
	 * @returns Object previous value assocated with specifed key, or null if there was no mapping for key.  A null return can also
	 * 		indicate that the mpa previously associated null with the specified key.
	 * @throws ClassCastException - key cannot be compared with the keys currently in the map.
	 * @throws NullPointerException - key is null and this map uses natural order, or its comparator does not tolerate null keys.
	 */
	public function remove( Object $key ) {
		$p = $this->getEntry( $key );
		if ($p == null)
			return null;
			
		$oldValue = $p->value;
		$this->deleteEntry( $p );
		return $oldValue;
	}
	
	/**
	 * Removes all mappings from this TreeMap.
	 * 
	 * @returns void
	 */
	public function clear() {
		$this->modCount++;
		$this->size = 0;
		$this->root = null;
	}
	
	/**
	 * Returns a Set view of the keys contained in this map.
	 *
	 * The set's iterator will return the keys in ascending order. The map is backed by this TreeMap instance, so changes to this 
	 * map are reflected in the Set, and vice-versa. The Set supports element removal, which removes the corresponding mapping 
	 * from the map, via the CollectionIterator.remove, Set.remove, removeAll, retainAll, and clear operations. It does not support the add 
	 * or addAll operations.
	 *
	 * @returns Set a set view of the keys contained in this TreeMap.
	 */
	public function keySet() {
		if ($this->key_set == null) {
			$this->key_set = new TreeMap_KeySet( $this );
		}	
		return $this->key_set;
	}
	
	/**
	 * Returns a collection view of the values contained in this map.
	 *
	 * The collection's iterator will return the values in the order that their corresponding keys appear in the tree. The 
	 * collection is backed by this TreeMap instance, so changes to this map are reflected in the collection, and vice-versa. 
	 * The collection supports element removal, which removes the corresponding mapping from the map through the CollectionIterator.remove,
	 * Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.
	 *
	 * @returns Collection a collection view of the values contained in this map.
	 */
	public function values() {
		if ($this->values == null) {
			$this->values = new TreeMap_ValueCollection( $this );
		}
		return $this->values;
	}
	
	/**
	 * Returns a set view of the mappings contained in this map.
	 *
	 * The set's iterator returns the mappings in ascending key order. Each element in the returned set is a Map.Entry. The set is 
	 * backed by this map, so changes to this map are reflected in the set, and vice-versa. The set supports element removal, 
	 * which removes the corresponding mapping from the TreeMap, through the CollectionIterator.remove, Set.remove, removeAll, retainAll and 
	 * clear operations. It does not support the add or addAll operations.
	 *
	 * @returns Set a set view of the keys contained in this TreeMap.
	 */
	public function entrySet() {
		if ($this->entry_set == null) {
			$this->entry_set = new TreeMap_EntrySet( $this );
		}
		return $this->entry_set;
	}
	
	/**
	 * Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive. (If fromKey and 
	 * toKey are equal, the returned sorted map is empty.)
	 * 
	 * The returned sorted map is backed by this map, so changes in the returned sorted map are reflected in this map, and 
	 * vice-versa. The returned sorted map supports all optional map operations.
	 * 
	 * The sorted map returned by this method will throw an IllegalArgumentException if the user attempts to insert a key less 
	 * than fromKey or greater than or equal to toKey.
	 * 
	 * Note: this method always returns a half-open range (which includes its low endpoint but not its high endpoint). If you need 
	 * a closed range (which includes both endpoints), and the key type allows for calculation of the successor a given key, 
	 * merely request the subrange from lowEndpoint to successor(highEndpoint). For example, suppose that m is a sorted map whose 
	 * keys are strings. The following idiom obtains a view containing all of the key-value mappings in m whose keys are between 
	 * low and high, inclusive:
	 * 
	 * SortedMap sub = m.submap(low, high+"\0");
	 * 
	 * A similar technique can be used to generate an open range (which contains neither endpoint). The following idiom obtains a
	 * view containing all of the key-value mappings in m whose keys are between low and high, exclusive:
	 * 
	 * SortedMap sub = m.subMap(low+"\0", high);
	 *
	 * @param Object $fromKey low endpoint (inclusive) of the subMap.
	 * @param Object $toKey high endpoint (exclusive) of the subMap.
	 * @returns SortedMap a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.
	 * @throws ClassCastException - if fromKey and toKey  cannot be compared to one another using this map's comparator (or, if 
	 * 		the map has no comparator, using natural ordering). 
	 * @throws IllegalArgumentException - if fromKey is greater than toKey. 
	 * @throws NullPointerException - if fromKey or toKey is null and this map uses natural order, or its comparator does 
	 *		not tolerate null keys.
	 */
	public function subMap( Object $fromKey, Object $toKey ) {
		return new SubMap( $fromKey, $toKey );
	}
	
	/**
	 * Returns a view of the portion of this map whose keys are strictly less than toKey. 
	 * 
	 * The returned sorted map is backed by this map, so changes in the returned sorted map are reflected in this map, and 
	 * vice-versa. The returned sorted map supports all optional map operations.
	 *
	 * The sorted map returned by this method will throw an IllegalArgumentException if the user attempts to insert a key greater 
	 * than or equal to toKey.
	 * 
	 * Note: this method always returns a view that does not contain its (high) endpoint. If you need a view that does contain 
	 * this endpoint, and the key type allows for calculation of the successor a given key, merely request a headMap bounded by
	 * successor(highEndpoint). For example, suppose that suppose that m is a sorted map whose keys are strings. The following idiom
	 * obtains a view containing all of the key-value mappings in m whose keys are less than or equal to high:
	 *
	 * SortedMap head = m.headMap(high+"\0");
	 * 
	 * @param Object $toKey high endpoint (exclusive) of the subMap.
	 * @returns SortedMap a view of the portion of this map whose keys are strictly less than toKey.
	 * @throws ClassCastException - if toKey is not compatible with this map's comparator (or, if the map has no comparator, if 
	 * 		toKey does not implement Comparable). 
	 * @throws IllegalArgumentException - if this map is itself a subMap, headMap, or tailMap, and toKey is not within the 
	 * 		specified range of the subMap, headMap, or tailMap. 
	 * @throws NullPointerException - if toKey is null and this map uses natural order, or its comparator does not tolerate 
	 * 		null keys.
	 */
	public function headMap( Object $toKey ) {
		return new SubMap( $toKey, true );
	}
	
	/**
	 * Returns a view of the portion of this map whose keys are greater than or equal to fromKey. 
	 * 
	 * The returned sorted map is backed by this map, so changes in the returned sorted map are reflected in this map, and 
	 * vice-versa. The returned sorted map supports all optional map operations.
	 * 
	 * The sorted map returned by this method will throw an IllegalArgumentException if the user attempts to insert a key less 
	 * than fromKey.
	 * 
	 * Note: this method always returns a view that contains its (low) endpoint. If you need a view that does not contain this 
	 * endpoint, and the element type allows for calculation of the successor a given value, merely request a tailMap bounded by 
	 * successor(lowEndpoint). For example, suppose that m is a sorted map whose keys are strings. The following idiom obtains a 
	 * view containing all of the key-value mappings in m whose keys are strictly greater than low:
	 * 
	 * SortedMap tail = m.tailMap(low+"\0");
 	 * 
	 * @param Object $fromKey low endpoint (inclusive) of the tailMap.
	 * @returns SortedMap a view of the portion of this map whose keys are greater than or equal to fromKey.
	 * @throws ClassCastException - if fromKey is not compatible with this map's comparator (or, if the map has no comparator, 
 	 * 		if fromKey does not implement Comparable).
	 * @throws IllegalArgumentException - if this map is itself a subMap, headMap, or tailMap, and fromKey is not within 
 	 * 		the specified range of the subMap, headMap, or tailMap.
	 * @throws NullPointerException -if fromKey is null and this map uses natural order, or its comparator does not tolerate 
 	 * 		null keys.
	 */
	public function tailMap( Object $fromKey ) {
		return new SubMap( $fromKey, false );
	}
	/**
	 * Compares two keys using the correct comparison method for this TreeMap.
	 */ 
	private function compare( Object $k1, Object $k2 ) {
		return ($this->comparator == null ? $k1->compareTo($k2) : $this->comparator->compare($k1, $k2));
	}
	
	/**
	 * Test two values for equality. Differs from o1.equals(o2) only in
	 * that it copes with with o1 properly.	
	 */ 
	private static function valEquals( Object $o1, Object $o2 ) {
		return ( $o1 == null ? $o2 == null : $o1->equals( $o2 ));
	}
	
		
	public function firstEntry() {
		$p = $this->root;
		if ($p != null)
			while ($p->left != null)
				$p = $p->left;
		return $p;
	}
	
	public function lastEntry() {
		$p = $this->root;
		if ($p != null)
			while ($p->right != null)
				$p = $p->right;
		return $p;
	}
	
	public function successor( TreeMap_Entry $t ) {
		if ($t == null)
			return null;
		else if ($t->right != null) {
			$p = $t->right;
			while ($p->left != null)
				$p = $p->left;
			return $p;
		} else {
			$p = $t->parent;
			$ch = $t;
			while ($p != null && $ch == $p->right) {
				$ch = $p;
				$p = $p->parent;
			}
			return $p;
		}
	}
	
	private static function colorOf( TreeMap_Entry $p = null ) {
		return ( $p == null ? BLACK : $p->color );
	}
	private static function parentOf( TreeMap_Entry $p = null ) {
		return ( $p == null ? null : $p->parent );
	}
	private static function setColor ( TreeMap_Entry $p = null, $c ) {
		if ($p != null) $p->color = $c;
	}
	private static function leftOf( TreeMap_Entry $p = null ) {
		return ($p == null) ? null : $p->left;
	}
	private static function rightOf( TreeMap_Entry $p = null ) {
		return ( $p == null) ? null : $p->right;
	}
	
	//////////// Tree Balancing functions  //////////////////////////////////////
	
	private function rotateLeft( TreeMap_Entry $p ) {
		$r = $p->right;
		$p->right = $r->left;
		if ($r->left != null)
			$r->left->parent = $p;
		$r->parent = $p->parent;
		if ($p->parent == null)
			$this->root = $r;
		else if ($p->parent->left == $p)
			$p->parent->left = $r;
		else
			$p->parent->right = $r;
		$r->left = $p;
		$p->parent = $r;
	}
	
	private function rotateRight( TreeMap_Entry $p ) {
		$l = $p->left;
		$p->left = $l->right;
		if ( $l->right != null)
			$l->right->parent = $p;
		$l->parent = $p->parent;
		if ($p->parent == null)
			$this->root = $l;
		else if ($p->parent->right == $p) 
			$p->parent->right = $l;
		else
			$p->parent->left = $l;
		$l->right = $p;
		$p->parent = $l;
	}
	
	private function fixAfterInsertion( TreeMap_Entry $x ) {
		$x->color = RED;
		
		while ($x != null && $x != $this->root && $x->parent->color == RED) {
			if (TreeMap::parentOf( $x ) == TreeMap::leftOf( TreeMap::parentOf( $x )) )  {
				$y = TreeMap::rightOf( TreeMap::parentOf( TreeMap::parentOf( $x ) ) );
				if ( TreeMap::colorOf($y) == RED) {
					TreeMap::setColor( TreeMap::parentOf($x), BLACK );
					TreeMap::setColor( $y, BLACK );
					TreeMap::setColor( TreeMap::parentOf( TreeMap::parentOf($x)), RED );
					$x = TreeMap::parentOf( TreeMap::parentOf( $x ));
				} else {
					if ($x == TreeMap::rightOf( TreeMap::parentOf( $x ))) {
						$x = TreeMap::parentOf(x);
						$this->rotateLeft($x);
					}
					TreeMap::setColor( TreeMap::parentOf($x ), BLACK);
					TreeMap::setColor( TreeMap::parentOf( TreeMap::parentOf( $x ) ), RED );
					if ( TreeMap::parentOf( TreeMap::parentOf( $x )) != null)
						$this->rotateRight( TreeMap::parentOf( TreeMap::parentOf( $x )) );
				}
			} else {
				$y = TreeMap::leftOf( TreeMap::parentOf( TreeMap::parentOf( $x ) ) );
				if ( TreeMap::colorOf($y) == RED) {
					TreeMap::setColor( TreeMap::parentOf($x), BLACK );
					TreeMap::setColor( $y, BLACK );
					TreeMap::setColor( TreeMap::parentOf( TreeMap::parentOf($x)), RED );
					$x = TreeMap::parentOf( TreeMap::parentOf( $x ));
				} else {
					if ($x == TreeMap::leftOf( TreeMap::parentOf( $x ))) {
						$x = TreeMap::parentOf( $x );
						$this->rotateRight($x);
					}
					TreeMap::setColor( TreeMap::parentOf($x ), BLACK);
					TreeMap::setColor( TreeMap::parentOf( TreeMap::parentOf( $x ) ), RED );
					if ( TreeMap::parentOf( TreeMap::parentOf( $x )) != null)
						$this->rotateLeft( TreeMap::parentOf( TreeMap::parentOf( $x )) );
				}
			}
		}
		$this->root->color = BLACK;
	}


	private function deleteEntry( TreeMap_Entry $p ) {
		$this->decrementSize();
		
		// If strictly internal, copy successor's element to p and then make p point to successor
		if ($p->left != null && $p->right != null) {
			$s = $this->successor( $p );
			$p->key = $s->key;
			$p->value = $s->value;
			$p = $s;
		} // p has 2 children
		
		$replacement = ( $p->left != null ? $p->left : $p->right );
		
		if ($replacement != null) {
			$replacement->parent = $p->parent;
			if ($p->parent == null)
				$this->root = $replacement;
			else if ($p == $p->parent->left)
				$p->parent->left = $replacement;
			else
				$p->parent->right = $replacement;
				
			// null out links so they are OK to be used by fixeAfterDeletion.
			$p->left = $p->right = $p->parent = null;
			
			// Fix replacement
			if ($p->color == BLACK)
				$this->fixAfterDeletion( $replacement );
		} else if ($p->parent == null) { // return if we are the only node.
			$this->root = null;
		} else { // No children.  Use self as phantom replacement and unlink.
			if ($p->color == BLACK)
				$this->fixAfterDeletion( $p );
				
			if ($p->parent != null) {
				if ($p == $p->parent->left)
					$p->parent->left = null;
				else if ($p == $p->parent->right)
					$p->parent->right = null;
				
				$p->parent = null;
			}
		}
	}
	
	private function fixAfterDeletion( TreeMap_Entry $x ) {
		while ($x != $this->root && TreeMap::colorOf( $x ) == BLACK) {
			if ($x == TreeMap::leftOf( TreeMap::parentOf( $x ) ) ) {
				$sib = TreeMap::rightOf( TreeMap::parentOf ($x ) );
				
				if ( TreeMap::colorOf( $sib ) == RED ) {
					TreeMap::setColor( $sib, BLACK );
					TreeMap::setColor( TreeMap::parentOf( $x ), RED );
					$this->rotateLeft( TreeMap::parentOf( $x ));
					$sib = TreeMap::rightOf( TreeMap::parentOf( $x ) );
				}
				
				if ( TreeMap::colorOf(TreeMap::leftOf( $sib )) == BLACK &&
					 TreeMap::colorOf(TreeMap::rightOf( $sib)) == BLACK) {
					TreeMap::setColor( $sib, RED );
					$x = TreeMap::parentOf( $x );	 
				} else {
					if ( TreeMap::colorOf( TreeMap::rightOf( $sib )) == BLACK) {
						TreeMap::setColor( TreeMap::leftOf( $sib ), BLACK );
						TreeMap::setColor( $sib, RED );
						$this->rotateRight( $sib );
						$sib = TreeMap::rightOf( TreeMap::parentOf( $x ));
					}
					TreeMap::setColor( $sib, TreeMap::colorOf( TreeMap::parentOf( $x )));
					TreeMap::setColor( TreeMap::parentOf( $x ), BLACK );
					TreeMap::setColor( TreeMap::rightOf( $x ), BLACK );
					$this->rotateLeft( TreeMap::parentOf( $x ));
					$x = $this->root;
				}
			} else {
				$sib = TreeMap::leftOf( TreeMap::parentOf( $x ));
				
				if ( TreeMap::colorOf( $sib ) == RED ) {
					TreeMap::setColor( $sib, BLACK );
					TreeMap::setColor( TreeMap::parentOf( $x ), RED );
					$this->rotateRight( TreeMap::parentOf( $x ));
					$sib = TreeMap::leftOf( TreeMap::parentOf( $x ));
				}
				
				if ( TreeMap::colorOf( TreeMap::rightOf( $sib )) == BLACK &&
					 TreeMap::colorOf( TreeMap::leftOf(  $sib )) == BLACK ) {
					TreeMap::setColor( $sib, RED );
					$x = TreeMap::parentOf( $x );	 
				} else {
					if ( TreeMap::colorOf( TreeMap::leftOf( $sib )) == BLACK ) {
						TreeMap::setColor( TreeMap::rightOf( $sib ), BLACK );
						TreeMap::setColor( $sib, RED );
						$this->rotateLeft( $sib );
						$sib = TreeMap::leftOf( TreeMap::parentOf( $x ));
					}
					TreeMap::setColor( $sib, TreeMap::colorOf( TreeMap::parentOf( $x )));
					TreeMap::setColor( TreeMap::parentOf( $x ), BLACK );
					TreeMap::setColor( TreeMap::leftOf( $sib ), BLACK );
					$this->rotateRight( TreeMap::parentOf( $x ));
					$x = $this->root;
				}
			}
		}
		
		TreeMap::setColor( $x, BLACK );
	}
}



/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: TreeMap.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class TreeMap_EntrySet extends AbstractSet {
	private $back;
	
	public function __construct( TreeMap $map ) {
		$this->back = $map;
	}
	public function iterator() {
		return new TreeMap_EntryIterator( $this->back );
	}
	public function contains( Object $o ) {
		if (! ($o instanceof MapEntry))
			return false;
		$entry = $o;
		$value = $entry->getValue();
		$p = $this->getEntry( $entry->getKey() );
		return ($p != null && $this->valEquals( $p->getValue(), $value ) );
	}
	
	public function remove( Object $o ) {
		if (! ( $o instanceof MapEntry ))
			return false;
		$entry = $o;
		$value = $entry->getValue();
		$p = $this->getEntry( $entry->getKey() );
		if ($p != null && $this->valEquals( $p->getValue(), $value)) {
			$this->deleteEntry( $p );
			return true;
		}
		return false;
	}
	
	public function size() {
		return $this->back->size();
	}
	
	public function clear() {
		return $this->back->clear();
	}
}




/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: TreeMap.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class TreeMap_ValueCollection extends AbstractCollection {
	private $back;
	
	public function __construct( TreeMap $map ) {
		$this->back = $map;
	}
	public function iterator() {
		return new TreeMap_ValueIterator( $this->back );
	}
	
	public function size() {
		return $this->back->size();
	}
	
	public function contains( Object $o ) {
		for ($e = $this->firstEntry(); $e != null; $e = $this->successor( $e ) )
			if ($this-valEquals( $e->getValue(), $o ))
				return true;
		return false;
	}
	
	public function remove( Object $o ) {
		for ($e = $this->firstEntry(); $e != null; $e = $this->successor( $e ) )
			if ($this->valEquals( $e->getValue(), $o )) {
				$this->deleteEntry( $e );
				return true;
			}
		return false;
	}
	
	public function clear() {
		$this->back->clear();
	}
}


/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: TreeMap.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class TreeMap_KeySet extends AbstractSet {
	private $back;
	
	public function __construct( TreeMap $map ) {
		$this->back = $map;
	}

	public function iterator() {
		return new TreeMap_KeyIterator( $this->back );
	}
	public function contains( Object $o ) {
		return $this->back->containsKey($o);
	}
	
	public function remove( Object $o ) {
		$oldSize = $this->back->size();
		$this->back->remove( $o );
		return $this->size() != $oldSize;
	}
	
	public function size() {
		return $this->back->size();
	}
	
	public function clear() {
		return $this->back->clear();
	}
}


/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: TreeMap.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class SubMap extends AbstractMap implements SortedMap {
	private $back = null;

	private $fromStart = false;
	private $toEnd = false;
	private $fromKey;
	private $toKey;
	
	private $entrySet = null;
	
	public function __construct( AbstractMap $back, Object $fromKey, Object $toKey ) {
		if ($this->compare($fromKey, $toKey) > 0)
			throw new IllegalArgumentException("fromKey > toKey");
			
		$this->back = $back;	
		$this->fromKey = $fromKey;
		$this->toKey = $toKey;
	}
	/*
	public function __construct( Object $key, $headMap ) {
		$this->compare( $key, $key );
		
		if ($headMap) {
			$this->fromStart = true;
			$this->toKey = $key;
		} else {
			$this->toEnd = true;
			$this->fromKey = $key;
		}
	}
	
	public function __construct( $fromStart, Object $fromKey, $toEnd, Object $toKey) {
		$this->fromStart 	= $fromStart;
		$this->fromKey		= $fromKey;
		$this->toEnd		= $toEnd;
		$this->toKey		= $toKey;
	}
	*/
	public function isEmpty() {
		return $this->entrySet->isEmpty();
	}
	
	public function containsKey( Object $key ) {
		return $this->inRange( $key ) && $this->back->containsKey( $key );
	}
	
	public function get( Object $key ) {
		if (! $this->inRange( $key ) )
			return null;
		return $this->back->get($key );
	}
	
	public function put( Object $key, Object $value ) {
		if (! $this->inRange( $key ))
			throw new IllegalArgumentException("key out of range");
		return $this->back->put( $key, $value );
	}
	
	public function comparator() {
		return $this->back->comparator();
	}
	
	public function firstKey() {
		$first = $this->key( $this->fromStart ? $this->firstEntry() : $this->getCeiling( $fromKey ));
		if (! $this->toEnd && $this->compare( $first, $toKey ) >= 0)
			throw new NoSuchElementException();
		return first;
	}
	
	public function lastKey() {
		$last = $this->key( $this->toEnd ? $this->lastEntry() : $this->getPrecedingEntry( $toKey ));
		if (! $this->fromStart && $this->compare( $last, $fromKey ) < 0)
			throw new NoSuchElementException();
		return last;
	}
	
	
	public function entrySet() {
		if ($this->entrySet == null)
			$this->entrySet = new TreeMap_EntrySetView( $this );
		return $this->entrySet;
	}
	
	
	public function subMap( Object $fromKey, Object $toKey ) {
		if (! inRange2( $fromKey ))
			throw new IllegalArgumentException("fromKey out of range");
		if (! inRange2( $toKey ))
			throw new IllegalArgumentException("toKey out of range");
			
		return new SubMap( $fromKey, $toKey );
	}
	
	public function headMap( Object $toKey) {
		if (! $this->inRange2($toKey))
			throw new IllegalArgumentException("toKey out of range");
	 	return new SubMap( $fromStart, $fromKey, false, $toKey);
	}

 	public function tailMap( Object $fromKey) {
 		if (! $this->inRange2($fromKey))
			throw new IllegalArgumentException("fromKey out of range");
 		return new SubMap(false, $fromKey, $toEnd, $toKey);
 	}

 	private function inRange( Object $key) {
 		return ( $this->fromStart || $this->compare($key, $this->fromKey) >= 0) &&
 			   ( $this->toEnd     || $this->compare($key, $this->toKey)   <  0);
 	}

 // This form allows the high endpoint (as well as all legit keys)
	private function inRange2( Object $key) {
 		return ( $this->fromStart || $this->compare($key, $this->fromKey) >= 0) &&
 			   ( $this->toEnd 	  || $this->compare($key, $this->toKey)   <= 0);
 	}
}



/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: TreeMap.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class TreeMap_EntrySetView extends AbstractSet {
	private $size = -1;
	private $sizeModCount;
	private $back;
	
	public function __construct( AbstractMap $map ) {
		$this->back = $map;
	}
	
	public function size() {
		if ( $this->size == -1 || $this->sizeModCount != $this->map->getModCount() ) {
			$this->size = 0;
			$this->sizeModCount = $this->map->getModCount();
			$i = $this->iterator();
			while ($i->hasNext() ) {
				$this->size++;
				$i->next();
			}	
		}
		return $this->size();
	}
	
	public function isEmpty() {
		return !$this->iterator()->hasNext();
	}
	
	public function contains( Object $o ) {
		if (!( $o instanceof MapEntry))
			return false;
			
		$entry = $o;
		$key = $entry->getKey();
		if (! $this->inRange( $key ))
			return false;
			
		$node = getEntry( $key );
		return $node != null && valEquals( $node->getValue, $entry->getValue() );
	}
	
	public function remove( Object $o ) {
		if (!( $o instanceof MapEntry))
			return false;
			
		$entry = $o;
		$key = $entry->getKey();
		if (! $this->inRange( $key ))
			return false;
			
		$node = getEntry( $key );
		if ($node != null && valEquals( $node->getValue, $entry->getValue() )) {
			deleteEntry( $node );
			return true;
		}	
		return false;
	}
	
	public function iterator() {
		return new TreeMap_SubMap_EntryCollectionIterator( 
			(fromStart ? firstEntry() : getCeilEntry(fromKey)),
				(toEnd ? null : getCeilEntry(toKey))); 
	}
	
	
}



/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: TreeMap.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class TreeMap_EntryIterator implements CollectionIterator {
	private $expectedModCount = 0;
	private $lastReturned = null;
	private $next;
	
	public function __construct( TreeMap $map, TreeMap_Entry $first = null ) {
		$this->back = $map;
		$this->expectedModCount = $this->back->getModCount();
		
		if ($first == null)
			$this->next = $this->back->firstEntry();
		else
			$this->next = first;
	}
		
	public function hasNext() {
		return $this->next != null;
	}
	
	public final function nextEntry() {
		if ($this->next == null) 
			throw new NoSuchElementException();
		if ( $this->back->getModCount() != $this->expectedModCount )
			throw new ConcurrentModificationException();
		$this->lastReturned = $this->next;
		$this->next = $this->back->successor($this->next);
		return $this->lastReturned;
	}
	
	public function getNext() {
		return $this->nextEntry();
	}
	public function next() {
		return $this->nextEntry();
	}
	
	public function current() {
	
	}
	public function key() {
	
	}
	public function valid() {
	
	}
	public function rewind() {
	
	}
	
	public function remove() {
		if ($this->lastReturned == null)
			throw new IllegalStateException();
		if ( $this->back->getModCount() != $this->expectedModCount)
			throw new ConcurrentModificationException();
		if ($this->lastReturned->left != null && $this->lastReturned->right != null)
			$this->next = $this->lastReturned;
		
		deleteEntry( $this->lastReturned );
		$this->expectedModCount++;
		$this->lastReturned = null;
	}
}


/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: TreeMap.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class TreeMap_KeyIterator extends TreeMap_EntryIterator {
	public function getNext() {
		return $this->nextEntry()->key;
	}
}


/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: TreeMap.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class TreeMap_ValueIterator extends TreeMap_EntryIterator {
	public function getNext() {
		return $this->nextEntry()->value;
	}
}


/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: TreeMap.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class TreeMap_SubMap_EntryIterator extends TreeMap_EntryIterator {
	private $firstExcludedKey;
	
	public function __construct( TreeMap_Entry $first, TreeMap_Entry $firstExcluded) {
		parent::__construct( $first );
		$this->firstExcludedKey = ($firstExcludedKey == null ? $firstExcluded : $firstExcluded->key);
	}
	
	public function hasNext() {
		return $this->next != null && $this->next->key != $this->firstExcludedKey;
	}
	
	public function next() {
		if ($this->next == null || $this->next->key == $this->firstExcludedKey )
			throw new NoSuchElementException();
		return $this->nextEntry();
	}
}


/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: TreeMap.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class TreeMap_Entry implements MapEntry {
	public $key;
	public $value;
	public $left = null;
	public $right = null;
	public $parent;
	public $color = BLACK;
	
	public function __construct( Object $key, Object $value, TreeMap_Entry $parent = null ) {
		$this->key = $key;
		$this->value = $value;
		$this->parent = $parent;
	}
	
	public function getKey() {
		return $this->key;
	}
	
	public function getValue() {
		return $this->value;
	}
	
	public function setValue( Object $value ) {
		$oldValue = $this->value;
		$this->value = $value;
		return $oldValue;
	}
	
	public function equals( Object $o ) {
		if (! ($o instanceof MapEntry))
			return false;
		$e = $o;
		
		return  TreeMap::valEquals( $this->key,   $e->getKey()   ) &&
				TreeMap::valEquals( $this->value, $e->getValue() );
	}
	
	public function hashCode() {
		$keyHash = ($this->key == null ? 0 : $this->key->hashCode() );
		$valueHash = ($this->value == null ? 0 : $this->value->hashCode() );
		return $keyHash ^ $valueHash;
	}
	
	public function toString() {
		return $this->key . "=" . $this->value;
	}
}


?>